package com.mxw.算法之美.a2链表;

import com.mxw.leetcode.B1链表.entity.ListNode;

public class 删除倒数第k个节点 {

    /**
     给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
     输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]

     难点：不知道链表的长度。首先要确定要删除节点的前后节点

     让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。
       1,2,3,4,5
     l     f

     1,2,3,4,5
         l    f

     *
     */

    public ListNode removeNthFromEnd(ListNode head, int n) {
        //新建一个虚拟头节点指向head
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        //快慢指针指向虚拟头节点
        ListNode fastIndex = dummyNode;
        ListNode slowIndex = dummyNode;

        // 只要快慢指针相差 n 个结点即可
        for (int i = 0; i <= n; i++) {
            fastIndex = fastIndex.next;
        }
        while (fastIndex != null) {
            fastIndex = fastIndex.next;
            slowIndex = slowIndex.next;
        }

        // 此时 slowIndex 的位置就是待删除元素的前一个位置。
        // 具体情况可自己画一个链表长度为 3 的图来模拟代码来理解
        // 检查 slowIndex.next 是否为 null，以避免空指针异常
        if (slowIndex.next != null) {
            slowIndex.next = slowIndex.next.next;
        }
        return dummyNode.next;
    }
}
